The present invention relates generally to data compression and decompression, and, in particular to a method and apparatus for entropy coding. The present invention also relates to a computer program product comprising a computer program for entropy coding.
A call for proposals for the new JPEG-2000 standard was recently issued and a draft standard has been published entitled xe2x80x9cInformation Technologyxe2x80x94JPEG 2000 Image coding Systemxe2x80x94JPEG 2000 Committee Draft version 1.0, Dec. 9, 1999xe2x80x9d (herein after referred to as JPEG2000).
JPEG2000 proposes that the whole image be divided into one or more image tile components, each of which are then 2-D discrete wavelet transformed. The transform coefficients of each image tile component are then grouped into sub-bands, which sub-bands are further partitioned into rectangular code blocks before each code block is then entropy encoded. The transform coefficients of each code block are expressed in a sign-magnitude representation prior to entropy coding. The entropy encoding consists of two parts: a context generator and an arithmetic coder. The arithmetic coder takes as input the bit symbol of a coefficient to be encoded and the context of that bit symbol. The context of a bit symbol of a coefficient, which bit symbol is to be coded by the arithmetic coder, is based on the xe2x80x98significancexe2x80x99 states of the 8 surrounding coefficients in the same bit-plane of the code block. The xe2x80x98significancexe2x80x99 state of a coefficient is a binary-valued variable Si[m,n], which is initialised to 0, but transitions to 1 immediately after the coefficient""s first non-zero bit value is encoded. FIG. 1 shows the neighbouring significance states Si[mxe2x88x921,nxe2x88x921], Si[mxe2x88x921,n] Si[mxe2x88x921,n+1], Si[m,nxe2x88x921] Si[m,n+1], Si[m+1,nxe2x88x921], Si[m+1,n] and Si[m+1,n+1] of the 8 surrounding coefficients of a coefficient xe2x80x9cX[m,n]xe2x80x9d, where m,n are the row and column numbers respectively of the code block and Si[ ] is the significance state immediately prior to the encoding of the bit symbol i of the coeficient X[m,n]. These neighbouring significance states are sometimes referred to as the significance states of the 3xc3x973 neighbourhood of the coefficient X[m,n].
The arithmetic coder first codes all the bit symbols of the most significant bit-plane of a code block, then all the bit symbols of the next lower bit-plane of the code block and so on to a least significant bit-plane. Within each bit-plane of a code block, the arithmetic coder codes the bit symbols of the coefficients in three passes in a predetermined order.
The first pass of a bitplane is called the significance propagation pass (SP pass), the second pass of the bitplane is called the magnitude refinement pass (MR pass), and the third and last pass of the bitplane is called the cleanup pass (N pass). During the SP pass, a bit symbol of the bitplane is encoded if the bit symbol to be encoded has a neighbouring bit symbol, which has a significance state of one(1) but has itself a significance state of zero(0). During the MR pass, a bit symbol of the bitplane is encoded, if not already encoded, if the coefficient of that bit symbol is already significant in the previous encoded bitplane. During the N pass, the remaining bit symbols of the bitplane that have not already been encoded are then encoded.
The context is delivered to the arithmetic coder along with the bit to be encoded and the encoded symbol is output to the bitstream. If the value of this bit symbol to be coded is one (1) and the significance state is zero then the significance state is set to one (1) once the bit symbol is coded and the next immediate bit symbol to be coded is the sign bit for the coefficient. Otherwise, the significance state remains zero (0). When the contexts of successive coefficients and passes are considered, the most current significance state for this coefficient is used.
The arithmetic coder codes the bit symbols of a bitplane in the three passes (SP, MR, and N) in the same predetermined order. The arithmetic coder first proceeds to the highest bitplane that has a non-zero bit in it and skips the SP, MR passes and commences with the N pass. The arithmetic coder then proceeds to the next lower bit plane and codes the bit symbols in the three passes (SP, MR, and N) in that order. It then proceeds to the next lower bit plane and codes the bit symbols in the same order of passes (SP, MR, and N) and so on to the least significant bitplane.
In addition, each bitplane of a code block is scanned in a particular order. Starting at the top left, the first four bit symbols of the column are scanned. Then the first four bit symbols of the second column, until the width of the code-block has been covered. Then the second four bit symbols of the first column are scanned and so on. A similar scan is continued for any leftover rows on the lowest code blocks in the sub-band. FIG. 2 shows an example of the code-block scan pattern for a code block having 64 transform coefficients arranged in an 8xc3x978 block. As can be seen in this example, the scanning is performed in consecutive strips of four rows. The code block is not limited to a 8xc3x978 block and larger code blocks are envisaged, such as 64xc3x9764 code block. In the latter case, there will 16 consecutive strips of four rows. For ease of explanation, this scanning order is herein after referred to as the JPEG2000 scanning order.
The entropy decoding described in JPEG2000 is a mirror image of the entropy encoding. For instance, the decoder decodes the symbols in the same order that they were encoded. The entropy decoding also comprises two sections: a context generator and an arithmetic decoder. The arithmetic decoder takes as input the symbol to be decoded and the context of that symbol to be decoded. The context of a symbol to be decoded, which symbol is to be decoded by the arithmetic decoder, is based on the xe2x80x98significancexe2x80x99 states of the 8 surrounding coefficients in the same bit-plane of the code block. The xe2x80x98significancexe2x80x99 state of a coefficient is a binary-valued variable S[m,n], which is initialised to 0, but transitions to 1 when the coefficient""s first non-zero bit-plane value is decoded. In this fashion, the significance states of the coefficients during the decoding phase mirrors the significance states of the coefficients during the encoding phase (see FIG. 2).
In JPEG2000 the arithmetic coding and decoding is performed bit-plane by bit-plane, from the most significant bit plane to the least significant bit plane. In the beginning the coding/decoding skips over all the bit planes with only zeroes in them, and would only begin operation on the first bit plane with non-zero elements in it. Once it reaches there, the codec operates on each successive bit-plane in three passes: significance propagation pass, magnitude refinement pass and cleanup pass.
A entropy codec has been proposed for implementing JPEG2000, which has the codec scanning through the whole bit-plane, and locating positions that have a certain characteristics. For example, in the significance propagation pass, the codec looks for positions that are not significant themselves, but have at least one significant coefficient in its 3xc3x973 neighbourhood. In the magnitude refinement pass, the codec looks for positions that are significant already. In the cleanup pass, the codec looks for positions that are not coded/decoded before. Therefore, in the proposed codec every bit plane is scanned three times. This implies that the maximum throughput is one symbol per three cycles.
As we can see from the above, the main problem in the proposed codec is that for each pass the codec needs to scan through all the positions and decides whether they are coded/decoded in the current pass. That means that cycles are wasted scanning through positions that need not be coded.
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements and/or proposals.
The present invention is a method for entropy coding symbols representative of a code block comprising transform coefficients of a digital image. The invention also includes a corresponding apparatus and a corresponding computer program product. Preferably, the method operates in a codec manner, in that the method is able to decode or encode the symbols performing substantially the same steps.
The entropy coding method processes each bitplane from a first bitplane to a predetermined minimum bitplane of the code block of transform coefficients. The entropy coding method generates a number of lists of positions of the coefficients in the block having symbols to be entropy encoded during the current bitplane of the block. The method then entropy codes the symbols of the coefficients in the current bitplane of the code block using the lists.
More specifically, the entropy coding method performs a significance propagation pass, a magnitude propagation pass, and a cleanup pass, in that order, for entropy coding the symbols of a code block. The entropy coding method generates prior to the current pass of the current bitplane, a list of those symbols to be entropy coded during the current pass. Specifically, the entropy coding method generates, prior to the significance propagation pass of a current bitplane, a first list of positions of those coefficients in the code block that have symbols to be entropy coded during the significance propagation pass of the current bitplane. The method also generates, prior to the magnitude refinement pass of the current bitplane, a second list of positions of those coefficients in the code block that have symbols to be entropy coded during the magnitude refinement pass of the current bitplane. The method further generates, prior to the cleanup pass of the current bitplane, a third list of positions of those coefficients in the code block that have symbols to be entropy coded during the cleanup pass of the current bitplane.
In this way, the entropy coding method is able to use the lists to directly access and entropy code the relevant symbols without scanning through all the symbols of the code block.